package com.dmall.graph.bfs.app;

import java.util.*;

/**
 * 农夫过河问题：农夫带了一只狼、一只羊和一筐白菜现在要过河，过河有条小船，只能承载农夫、狼、羊、白菜中的两样，
 * 但是在农夫不在的情况下狼要吃羊，羊要吃白菜，且过河必须要有农夫划船，试问在保证羊和白菜完整的情况下，如果过河？
 *
 * 状态定义：未过河的状态定义为0，过河的状态定义为1，
 * 那么0000表示都未过河，1111表示过河成功，初始状态为0000，最终状态为1111
 * 0000或者1111的第一位表示农夫，第二位表示狼，第三位表示羊，第四位表示白菜
 */
public class FarmerCrossRiverPuzzle {

    private static final String start = "0000";
    private static final String end = "1111";
    private static final Set<String> deadendSet = new HashSet<>();

    static {
        deadendSet.add("1000");
        deadendSet.add("0111");
        deadendSet.add("1100");
        deadendSet.add("0011");
        deadendSet.add("1001");
        deadendSet.add("0110");
    }

    private int stepCount = -1;
    private Map<String, String> pre = new HashMap<>();

    public FarmerCrossRiverPuzzle() {
        Map<String, Integer> visited = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(start);
        visited.put(start, 0);
        pre.put(start, start);
        while (!queue.isEmpty()) {
            String cur = queue.remove();
            for (String next : getNexts(cur)) {
                if (!visited.containsKey(next) && !deadendSet.contains(next)) {
                    queue.add(next);
                    visited.put(next, visited.get(cur) + 1);
                    pre.put(next, cur);
                    if (next.equals(end)) {
                        stepCount = visited.get(next);
                        return;
                    }
                }
            }
        }
    }

    private Set<String> getNexts(String cur) {
        Set<String> set = new HashSet<>();
        char[] chars = cur.toCharArray();
        char char_1 = chars[1];
        char char_2 = chars[2];
        char char_3 = chars[3];

        // 农夫一个人划船过河
        chars[0] = Character.forDigit((chars[0] - '0' + 1) % 2, 10);
        set.add(new String(chars));

        // 农夫带着狼过河
        chars[1] = Character.forDigit((chars[1] - '0' + 1) % 2, 10);
        set.add(new String(chars));
        chars[1] = char_1;

        // 农夫带着羊过河
        chars[2] = Character.forDigit((chars[2] - '0' + 1) % 2, 10);
        set.add(new String(chars));
        chars[2] = char_2;

        // 农夫带着菜过河
        chars[3] = Character.forDigit((chars[3] - '0' + 1) % 2, 10);
        set.add(new String(chars));
        chars[3] = char_3;

        return set;
    }

    public int stepCount() {
        return stepCount;
    }

    public Iterable<String> results() {
        ArrayList<String> res = new ArrayList<>();
        if (stepCount == -1) {
            return res;
        }

        String cur = end;
        while (!cur.equals(start)) {
            res.add(cur);
            cur = pre.get(cur);
        }
        res.add(start);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        FarmerCrossRiverPuzzle farmerCrossRiverPuzzle = new FarmerCrossRiverPuzzle();
        System.out.println(farmerCrossRiverPuzzle.stepCount());
        System.out.println(farmerCrossRiverPuzzle.results());
    }
}
